package com.github.yangyishe.p400;

/**
 * 322. 零钱兑换
 * https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 *
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 *
 * 输入：coins = [1], amount = 0
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 231 - 1
 * 0 <= amount <= 104
 */
public class Problem322 {
    public static void main(String[] args) {
        int[] coins=new int[]{1};
        int amount=0;

        Problem322 problem322 = new Problem322();
        int coinChange = problem322.coinChange(coins, amount);
        System.out.println("coinChange = " + coinChange);

    }

    /**
     * 思路:
     * 由于coins数量多的情况可以参考少的情况, 且不会对少的情况产生影响, 所以可以使用动态规划
     * 将coins的种类按照给定顺序排序.
     * 创建一个二维数组, row表示使用到第几种coin, col表示当前coins情况所需的最少硬币数.
     * 如实例1中. 对应的硬币为1,2,5
     * row=1时, col分别为: 0,1,2,3,4,5,6,...,11
     * row=2时, col分别为: 0,1,1,2,2,3,3,....,6
     * row=3时, col分别为: 0,1,1,2,2,1,2,.....,3
     *
     * 在遍历新的一行是, 如果硬币值>amount,则情况与上一行相同
     * 否则, 为Math.min(result[row-1,col],result[row,col-coin[n]])
     * 如果遇到-1的情况就不予考虑. 如果两个值都是-1, 则仍为-1
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        //1. 创建初始数组
        int[][] results=new int[coins.length+1][amount+1];
        for(int i=1;i<=amount;i++){
            results[0][i]=-1;
        }

        //2. 分别开始推演遍历
        for(int row=1;row<=coins.length;row++){
            int curCoin = coins[row - 1];
            for(int col=1;col<=amount;col++){
                //上一次最小值
                int lastRowMin = results[row - 1][col];

                // 考虑增加当前硬币的最小值
                if(curCoin >col){
                    results[row][col]=lastRowMin;
                }else{
                    int lastColMin = results[row][col - curCoin];
                    if(lastColMin==-1){
                        results[row][col]=lastRowMin;
                    }else if(lastRowMin==-1){
                        results[row][col]=lastColMin+1;
                    }else{
                        results[row][col]=Math.min(lastRowMin,lastColMin+1);
                    }
                }

            }
        }

        return results[coins.length][amount];
    }
}
